import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;

public class Test {
    //一维前缀和
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] arr = new int[n];
        long[] dp = new long[n + 1];
        // 下标从一开始是因为要处理边界情况
        for(int i = 0;i < n ;i++){
            arr[i] = sc.nextInt();
            dp[i + 1] = dp[i] + arr[i];
        }
        while(q > 0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            long sum = dp[r] - dp[l - 1];
            System.out.println(sum);
            q--;
        }
    }

    //二维前缀和
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        int[][] arr = new int[n][m];
        long[][] dp= new long[n+1][m+1];

        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                arr[i][j] = in.nextInt();
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + arr[i][j];
            }
        }

        while(q > 0){
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();
            long sum = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1-1][y1-1];
            System.out.println(sum);
            q--;
        }
    }

    // 寻找数组的中心下标
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        // 算的是0~n-1的前缀和 没必要加1
        int[] f = new int[n];//前缀和
        int[] g = new int[n];//后缀和
        for(int i = 0;i < n -1;i++){
            f[i+1] = f[i] + nums[i];
        }
        for(int i = n - 1;i > 0;i--){
            g[i-1] = g[i] + nums[i];
        }
        for(int i = 0;i < n;i++){
            if(f[i] == g[i]) return i;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        int[] ret = productExceptSelf(nums);
        System.out.println(ret.toString());
    }
    //除自身以外数组的乘积
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];//前缀和
        int[] g = new int[n];//后缀和
        int[] ret = new int[n];
        // f[0]和g[n-1]应该为1
        f[0] = 1;
        g[n-1] = 1;
        //注意边界问题
        for(int i = 1;i < n;i++){
            f[i] = f[i-1] * nums[i-1];
        }

        for(int i = n-2;i >= 0;i--){
            g[i] = g[i+1] * nums[i+1];
        }

        for(int i = 0;i < n;i++){
            ret[i] = f[i] * g[i];
        }

        return ret;
    }

    // 和为k的子数组
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        hash.put(0,1);
        int sum = 0,ret = 0;
        for(int x : nums){
            sum += x; // 计算当前位置的前缀和
            ret += hash.getOrDefault(sum - k,0);// 统计结果
            hash.put(sum,hash.getOrDefault(sum,0) + 1);// 把当前的前缀和丢到哈希表中
        }
        return ret;
    }

    // 和可被k整除的子数组
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
        hash.put(0 % k , 1);

        int sum = 0,ret = 0;
        for(int x : nums){
            sum += x;// 计算当前位置的前缀和
            int r = (sum % k + k) % k;
            ret += hash.getOrDefault(r,0);// 统计结果
            hash.put(r,hash.getOrDefault(r,0) + 1); // 将当前位置的前缀和放到哈希表里
        }

        return ret;
    }

    //连续数组
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
        hash.put(0,-1);

        int sum = 0,ret = 0;
        for(int i = 0;i < nums.length;i++){
            sum += (nums[i] == 0 ? -1:1);
            if(hash.containsKey(sum)) ret = Math.max(ret,i - hash.get(sum));
            else hash.put(sum,i);
        }

        return ret;

    }

    // 矩阵区域和
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;

        // 1. 预处理一个前缀和数组
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
                        + mat[i - 1][j - 1];
            }
        }

        // 2.使用前缀和数组
        int[][] ret = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int x1 = Math.max(0,i - k) + 1, y1 = Math.max(0,j - k) + 1;
                int x2 = Math.min(m - 1,i + k) + 1, y2 = Math.min(n - 1,j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2]
                        + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }




}
